# LeetCode 718、最长重复子数组

# 一、题目描述

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

提示：

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长重复子数组（ LeetCode 718 ）：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
class Solution {
    public int findLength(int[] nums1, int[] nums2) {

        // 获取 nums1 的长度
        int m = nums1.length;
        
        // 获取 nums2 的长度
        int n =  nums2.length;
        
        // 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
        // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
        // 前 i 个元素的区间为 [ 0 ， i - 1 ]
        // dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
        // 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
        // 因此，dp 数组的长度为 m + 1 和 n + 1
        int[][] dp = new int[m + 1][n + 1];

        // maxLength 表示 dp 数组中的最大值
        int maxLength = 0;
        
        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // nums1 nums2 也没有元素
        // 因此，公共的、长度最长的子数组的长度为 0
        dp[0][0] = 0;

        // nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
        for( int i = 0 ; i <= m ; i++){
            dp[i][0] = 0;
        }

        for( int j = 0 ; j <= n ; j++){
            dp[0][j] = 0;
        }

        // i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
        for (int i = 1; i <= m; i++) {

            // j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
            for (int j = 1; j <= n; j++) {

                // 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
                // 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
                // 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
                if (nums1[i - 1] == nums2[j - 1]) {

                    // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
                    // dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    // 更新最长的子数组长度
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        
        // 返回结果
        return maxLength;
    }
}

# 2、C++ 代码

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // 获取 nums1 的长度
        int m = nums1.size();
        
        // 获取 nums2 的长度
        int n =  nums2.size();
        
        // 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
        // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
        // 前 i 个元素的区间为 [ 0 ， i - 1 ]
        // dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
        // 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
        // 因此，dp 数组的长度为 m + 1 和 n + 1
        auto dp = vector < vector < int>> ( m + 1 ,vector<int> ( n + 1 ));

        // maxLength 表示 dp 数组中的最大值
        int maxLength = 0;
        
        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // nums1 nums2 也没有元素
        // 因此，公共的、长度最长的子数组的长度为 0
        dp[0][0] = 0;

        // nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
        for( int i = 0 ; i <= m ; i++){
            dp[i][0] = 0;
        }

        for( int j = 0 ; j <= n ; j++){
            dp[0][j] = 0;
        }

        // i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
        for (int i = 1; i <= m; i++) {

            // j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
            for (int j = 1; j <= n; j++) {

                // 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
                // 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
                // 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
                if (nums1[i - 1] == nums2[j - 1]) {

                    // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
                    // dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    // 更新最长的子数组长度
                    maxLength = max(maxLength, dp[i][j]);
                }
            }
        }
        
        // 返回结果
        return maxLength;

    }
};

# 3、Python 代码

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # 获取 nums1 的长度
        m = len(nums1)
        
        # 获取 nums2 的长度
        n = len(nums2)
        
        # 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
        # dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        # dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
        # dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
        # 前 i 个元素的区间为 [ 0 ， i - 1 ]
        # dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
        # 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
        # 因此，dp 数组的长度为 m + 1 和 n + 1
        dp = [[0] * (n + 1 ) for _ in range( m + 1 )]

        # maxLength 表示 dp 数组中的最大值
        maxLength = 0
        
        # dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        # nums1 nums2 也没有元素
        # 因此，公共的、长度最长的子数组的长度为 0
        dp[0][0] = 0

        # nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
        for i in range( 0 , m + 1 ) : 
            dp[i][0] = 0
        

        for j in range( 0 , n + 1 ) : 
            dp[0][j] = 0
        

        # i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
        for i in range( 1 , m + 1 ) : 

              # j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
              for j in range( 1 , n + 1 ) : 

                # 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
                # 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
                # 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
                if  nums1[i - 1] == nums2[j - 1] : 

                    # dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
                    # dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
                    dp[i][j] = dp[i - 1][j - 1] + 1

                    # 更新最长的子数组长度
                    maxLength = max(maxLength, dp[i][j])

        
        # 返回结果
        return maxLength

← LeetCode 174、地下城游戏 LeetCode 5、最长回文子串 →

# LeetCode 718、最长重复子数组

# 一、题目描述

# 二、题目解析

# 三、参考代码

# 1、Java 代码

# **2、**C++ 代码

# 3、Python 代码

# 2、C++ 代码